//
// Created by francklinson on 2021/10/21 AT 16:16.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        // 从左下角出发 大了就上移 小了就右移 充分利用矩阵的性质
        // 精彩
        int m = matrix.size(), n = matrix[0].size();
        int r = m - 1, c = 0; // 从矩阵的左下角开始
        while (r >= 0 and c < n) {
            if (matrix[r][c] < target)
                ++c;
            else if (matrix[r][c] > target)
                --r;
            else
                return true;
        }
        return false;
    }
};

int main() {
    vector<vector<int>> mat{{1,  4,  7,  11, 15},
                            {2,  5,  8,  12, 19},
                            {3,  6,  9,  16, 22},
                            {10, 13, 14, 17, 24},
                            {18, 21, 23, 26, 30}};
    Solution solution;
    cout << solution.searchMatrix(mat, 9) << endl;
    return 0;
}

